#include<iostream>
#include<stack>
using namespace std;

struct T_Hanoi
{
    int flag;   //0-左递归，1-右递归
    int disks;

    char source;
    char past;
    char target;
};

void Hanoi(int num, char source, char past, char target)
{
    stack<T_Hanoi> stkHanoi;

    char from = source;
    char temp = past;
    char to = target;

    do
    {
        while (num > 0)
        {
            T_Hanoi tHanoi = {0, num, from, temp, to};
            stkHanoi.push(tHanoi);

            //swap the past and target，A-B-C的第一步是A-C-B
            char c = temp;
            temp = to;
            to = c;

            num--;
        }

        T_Hanoi tTop = stkHanoi.top();
        stkHanoi.pop();
        cout<< tTop.source << "-->" << tTop.target <<endl;

        while (!stkHanoi.empty())
        {
            tTop = stkHanoi.top();
            stkHanoi.pop();

            if (0 == tTop.flag)
            {
		//A-B-C的第二步，source上只有一个盘子，可直接移动
                cout<< tTop.source << "-->"<< tTop.target <<endl;

                tTop.flag = 1;
                stkHanoi.push(tTop);

		//A-B-C的最后一步，B-A-C
                from = tTop.past;
                temp = tTop.source;
                to = tTop.target;

                num = tTop.disks - 1;

                break;
            }
        }
    }while (!stkHanoi.empty());
}

int main()
{

    Hanoi(4, 'A', 'B', 'C');

    return 0;
}

